package main

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// 不太对，运行不通过
func BuildTree(preorder []int, inorder []int) *TreeNode {
	//https://blog.csdn.net/qq_56460466/article/details/136186001
	//前序遍历的顺序是：根节点->左子树->右子树 中序遍历的顺序是：左子树->根节点->右子树
	// 所以我们可以使用前序遍历确定树及其子树的根节点，利用中序遍历与之前确定下来的根节点来确定左右子树的范围
	idxmap := map[int]int{}
	size := len(inorder)
	for i := 0; i < size; i++ {
		idxmap[inorder[i]] = i
	}

	return f(preorder, 0, size-1, inorder, 0, size-1, idxmap)
}

func f(parr []int, l1, r1 int, inarr []int, l2, r2 int, idxmap map[int]int) *TreeNode {
	if l1 > r1 {
		return nil
	}
	if l1 == r2 {
		return &TreeNode{parr[l1], nil, nil}
	}

	root := &TreeNode{parr[l1], nil, nil}
	idx := idxmap[parr[l1]]

	root.Left = f(parr, l1+1, l1+idx-l2, inarr, l2, idx-1, idxmap)
	root.Right = f(parr, l1+idx-l2+1, r2, inarr, idx+1, r2, idxmap)
	return root
}
